package com.example.stack;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 有效括号字符串为空 ""、"(" + A + ")" 或 A + B ，其中 A 和 B 都是有效的括号字符串，+ 代表字符串的连接。
 *  例如，""，"()"，"(())()" 和 "(()(()))" 都是有效的括号字符串。
 *  如果有效字符串 s 非空，且不存在将其拆分为 s = A + B 的方法，我们称其为原语（primitive），其中 A 和 B 都是非空有效括号字符串。
 *  给出一个非空有效字符串 s，考虑将其进行原语化分解，使得：s = P_1 + P_2 + ... + P_k，其中 P_i 是有效括号字符串原语。
 *  对 s 进行原语化分解，删除分解中每个原语字符串的最外层括号，返回 s 。
 *
 *  示例 1：
 * 输入：s = "(()())(())"
 * 输出："()()()"
 * 解释：
 * 输入字符串为 "(()())(())"，原语化分解得到 "(()())" + "(())"，
 * 删除每个部分中的最外层括号后得到 "()()" + "()" = "()()()"。
 *
 *  示例 2：
 * 输入：s = "(()())(())(()(()))"
 * 输出："()()()()(())"
 * 解释：
 * 输入字符串为 "(()())(())(()(()))"，原语化分解得到 "(()())" + "(())" + "(()(()))"，
 * 删除每个部分中的最外层括号后得到 "()()" + "()" + "()(())" = "()()()()(())"。
 *
 *  示例 3：
 * 输入：s = "()()"
 * 输出：""
 * 解释：
 * 输入字符串为 "()()"，原语化分解得到 "()" + "()"，
 * 删除每个部分中的最外层括号后得到 "" + "" = ""。
 */
public class Leetcode1021_RemoveOuterParentheses {
    public static void main(String[] args) {

        String str = "(()())(())";
        str= "(()())(())(()(()))";
        System.out.println(new Solution().removeOuterParentheses(str));

    }

    static class Solution {

        /**
         * 解法二:使用栈
         * @param s
         * @return
         */
        private String removeOuterParentheses2(String s) {
            char[] chars = s.toCharArray();
            StringBuilder sb = new StringBuilder();
            Deque<Character> stack = new LinkedList<>();
            int lastOpr = 0; // 用于记录原语子串开始的位置
            for (int i = 0; i < chars.length; i++) {
                if (chars[i] == '(') stack.push(chars[i]);
                else stack.pop();

                if (stack.isEmpty()) {
                    sb.append(chars, ++lastOpr, i - lastOpr);
                    lastOpr = i + 1;
                }

            }
            return sb.toString();
        }


        /**
         * 解法一:
         * 找到每个原语字符串，然后去掉头尾加入到结果集中
         *
         * 使用一个计数器
         * 遍历字符串，读取到左括号时计数器自增，读到右括号时计数器
         * 检查是否到达原语结尾（计数器为0时），截取不包含最外层的原语子串并拼接到容器中
         * @param s
         * @return
         */
        private String removeOuterParentheses1(String s) {
            int count = 0;
            int lastOpr = 0;
            StringBuilder sb = new StringBuilder();
            char[] chars = s.toCharArray();
            for (int i = 0; i < chars.length; i++) {

                if (chars[i] == '(')
                    count++;
                else
                    count--;

                if (count == 0) {
                    sb.append(chars, lastOpr + 1, i - lastOpr - 1);
//                    sb.append(s.substring(++lastOpr, i));
                    lastOpr = i + 1;
                }

            }
            return sb.toString();
        }

        public String removeOuterParentheses(String s) {
            return removeOuterParentheses2(s);
        }
    }
}
